{
 "cells": [
  {
   "cell_type": "markdown",
   "id": "62390202",
   "metadata": {},
   "source": [
    "# 4. 字符串操作\n",
    "- 字符串操作中常涉及多种算法，如滑动窗口、栈等，部分常见的试题如下：\n",
    "- leetcode: 93, 43, 227\n",
    "\n",
    "### 4.1 最长回文字符串\n",
    "> https://leetcode-cn.com/problems/longest-palindromic-substring/\n",
    "\n",
    "- example 1：\n",
    "```\n",
    "输入：s = \"babad\"\n",
    "输出：\"bab\"\n",
    "解释：\"aba\" 同样是符合题意的答案。\n",
    "```\n",
    "- example 2：\n",
    "```\n",
    "输入：s = \"cbbd\"\n",
    "输出：\"bb\"\n",
    "```"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "id": "42d1525b",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "result: cdfeefdc\n"
     ]
    }
   ],
   "source": [
    "# 解题思路：双指针, 考虑沿着中间对称，当偶数情形则从i，i+1 左右加减k\n",
    "class Solution:\n",
    "    def find_string(self, s, i, j):\n",
    "        length = len(s)\n",
    "        result = s[0]\n",
    "        for k in range(min(i+1, length - j)):\n",
    "            if s[i - k] == s[j + k]:\n",
    "                if (2*k + j-i+1) > len(result):\n",
    "                    result = s[i - k: j + k + 1]\n",
    "            else:\n",
    "                # 如果存在一个不满足要求则退出\n",
    "                break\n",
    "        return result\n",
    "\n",
    "    def longestPalindrome(self, s: str) -> str:\n",
    "        ret = s[0]\n",
    "        for i in range(len(s)):\n",
    "            # 查找基于中间对称，左右字符依次相等的最长字符串\n",
    "            # 针对可能为偶数的情形，则分别从i, i+1的位置分别加减k\n",
    "            str_1 = self.find_string(s, i, i)\n",
    "            str_2 = self.find_string(s, i, i + 1)\n",
    "            if len(str_1) > len(ret):\n",
    "                ret = str_1\n",
    "            if len(str_2) > len(ret):\n",
    "                ret = str_2\n",
    "\n",
    "        return ret\n",
    "\n",
    "data = \"sacdfeefdcuia\"\n",
    "S = Solution()\n",
    "result = S.longestPalindrome(data)\n",
    "print(\"result:\", result)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "ed335857",
   "metadata": {},
   "source": [
    "### 4.2 字符串相乘\n",
    "\n",
    "> leetcode: https://leetcode-cn.com/problems/multiply-strings/\n",
    "\n",
    "> 解题思路：字符串相乘，主要考虑类似乘法竖式的方式进行相乘，对比可将每一位上的数字依次存起来，用于进行竖式相乘。\n",
    "\n",
    "- example 1:\n",
    "```\n",
    "输入: num1 = \"2\", num2 = \"3\"\n",
    "输出: \"6\"\n",
    "```\n",
    "- example 2\n",
    "```\n",
    "输入: num1 = \"123\", num2 = \"456\"\n",
    "输出: \"56088\"\n",
    "```"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 35,
   "id": "17670645",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "'7695'"
      ]
     },
     "execution_count": 35,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "class Solution:\n",
    "    def multiply(self, num1: str, num2: str) -> str:\n",
    "        data1, data2 = [], []\n",
    "        # ord('0') is 48\n",
    "        for item in num1:\n",
    "            data1.append(ord(item) - 48)\n",
    "        for item in num2:\n",
    "            data2.append(ord(item) - 48)\n",
    "\n",
    "        mul_num1 = data1\n",
    "        mul_num2 = data2   # the smaller number\n",
    "        if len(data1) < len(data2):\n",
    "            mul_num2 = data1\n",
    "            mul_num1 = data2\n",
    "\n",
    "        res = []\n",
    "        mul_num2.reverse()\n",
    "        bit = 0\n",
    "        for i in mul_num2:\n",
    "            temp_res = self.calc(i, mul_num1)\n",
    "            for a in range(bit):\n",
    "                temp_res.append(0)\n",
    "            bit = bit + 1\n",
    "            temp_res.reverse()\n",
    "            res.append(temp_res)\n",
    "\n",
    "        data = self.add(res)\n",
    "\n",
    "        calc_res = \"\"\n",
    "        len_data = len(data)\n",
    "        for d, item in enumerate(data):\n",
    "            # 对于最开始前面为0的则去除\n",
    "            if item == 0 and len(calc_res) == 0 and d != (len_data - 1):\n",
    "                continue\n",
    "            calc_res = calc_res + str(item)\n",
    "\n",
    "        # print(\"res:\", calc_res)\n",
    "        return calc_res\n",
    "\n",
    "    def calc(self, k, num_list):\n",
    "        # print(\"input:\", k, num_list)\n",
    "        ret = []\n",
    "        bigger = 0\n",
    "        # 反过来取数据\n",
    "        for item in num_list[::-1]:\n",
    "            temp = k * item + bigger\n",
    "            ret.append(temp % 10)\n",
    "            bigger = temp // 10\n",
    "\n",
    "        if bigger > 0:\n",
    "            ret.append(bigger)\n",
    "        ret.reverse()\n",
    "        # print(\"ret:\", ret)\n",
    "        return ret\n",
    "\n",
    "    def add(self, num_list):\n",
    "        ret = []\n",
    "        len_list = []\n",
    "        for item in num_list:\n",
    "            len_list.append(len(item))\n",
    "\n",
    "        # print(\"num_list:\", num_list)\n",
    "        bigger = 0\n",
    "        for i in range(max(len_list)):\n",
    "            temp = 0\n",
    "            for d, k in enumerate(num_list):\n",
    "                if i < len_list[d]:\n",
    "                    temp = temp + k[i]\n",
    "\n",
    "            temp = temp + bigger\n",
    "            ret.append(temp % 10)\n",
    "            bigger = temp // 10\n",
    "\n",
    "        if bigger > 0:\n",
    "            ret.append(bigger)\n",
    "        ret.reverse()\n",
    "        return ret\n",
    "\n",
    "num1 = \"95\"\n",
    "num2 = \"81\"\n",
    "# calc(5, [6, 7])\n",
    "S = Solution()\n",
    "S.multiply(num1, num2)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "f708ab21",
   "metadata": {},
   "outputs": [],
   "source": []
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3 (ipykernel)",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.7.3"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 5
}
